package LeetCode._04动态规划_;

import java.util.Arrays;

public class _931_下降路径最小和 {
    /*
        dp:从第一行matrix[0][i]向下落，落到位置matrix[i][j]的最小路径和为dp(matrix,i,j)
     */
    int[][] memo;
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length; //控制dp数组大小
        int res = Integer.MAX_VALUE; //返回结果
        memo = new int[n][n];
        for(int i=0;i<n;++i){
            Arrays.fill(memo[i],55555);
        }
        //最终结果可能在最后一行的任意一列上
        for(int j=0;j<n;++j){
            res = Math.min(res,dp(matrix,n-1,j));
        }
        return res;
    }

    /**
     * 从第一行matrix[0][i]向下落，落到位置matrix[i][j]的最小路径和为dp(matrix,i,j)
     * @param matrix 路径数组
     * @param i 所在行
     * @param j 所在列
     * @return 当前所在行所在列计算的最小路径和
     */
    int dp(int[][] matrix,int i,int j){
        //安全性检查
        if(i<0 || j<0 || i>=matrix.length || j>= matrix[0].length) return 78787;
        //base case
        if(i == 0){
            return matrix[0][j];
        }

        //查看备忘录,防止重复计算
        if(memo[i][j]!=55555){
            return memo[i][j];
        }

        //状态转移
        //当前所在行所在列的最小路径和为当前值加上min(上方，左上方，右上方)的值
        memo[i][j] = matrix[i][j] + min(
                dp(matrix,i-1,j),
                dp(matrix,i-1,j-1),
                dp(matrix,i-1,j+1)
        );
        return memo[i][j];
    }

    //三个数找最小值
    int min(int a,int b,int c){
        return Math.min(a,Math.min(b,c));
    }
}
